1. Field of the Invention
The present invention generally relates to the field of logic devices. More particularly, the present invention is directed to a system and method for dynamically executing a function in a programmable logic array.
2. Background of the Invention
Recently, programmable logic devices, such as field programmable gate arrays (FPGAs), have evolved into devices capable of being dynamically reconfigured on a cycle-by-cycle basis to perform logic functions, or portion(s) thereof, during each cycle. With the increasing speed of such reconfigurable FPGAs (RFPGAs), RFPGAs are now being considered as components suitable for use in application specific integrated circuits (ASICs) and other integrated circuits (ICs). For example, ICs for applications that require certain data to be manipulated iteratively in order to produce a desired output are ICs that can benefit from the utilization of RFPGAs. Examples of such applications include communication protocol processing and image processing, among others.
A benefit of using an RFPGA to perform one or more functions that would otherwise be performed by fixed logic is often a reduction in the amount of chip area needed to perform these functions. For example, a certain function may be partitioned into ten functional blocks that are chained together such that the output of one block becomes the input to the next block, and so on. Using conventional fixed logic, all ten of these functional blocks would typically be placed on the chip next to one another in their proper data-flow sequence. Using an RFPGA solution, however, these ten functional blocks can be replaced with a single RFPGA that is cyclically reconfigured to process each of the ten functional blocks in the proper sequence.
Generally, the processing of the ten functional block function proceeds as follows. The RFPGA is configured for the first functional block and the input data of the function is passed into the RFPGA, i.e., the first functional block. The output of the first functional block then passes out of the block and is stored in certain storage elements created within the RFPGA. These storage elements store the output of the first functional block for use as the input to the second functional block of the function, which is created by reconfiguring portions of the RFPGA other than storage elements. At the same time portions of the RFPGA are being reconfigured for the second functional block, other portions of the RFPGA are reconfigured as storage elements for storing the output of the second functional block, which is also the input for the third functional block. This process is repeated for the third through the ninth functional blocks. The process for the tenth, and final, functional block is slightly different, with the output of the tenth functional block being passed to the external I/O elements of the RFPGA, where the output is passed to other portions of the IC.
While processing multiple functional blocks in series using an RFPGA is conceptually straightforward, conventional RFPGA reconfiguration techniques make it difficult to optimize each of the various configurations of the RFPGA needed to perform a given function. However, optimizing IC designs is important. This difficulty in optimizing configurations of an RFPGA is largely due to the way in which conventional techniques handle the data being passed from one configuration of logic, i.e., functional block, to the next configuration of logic.
FIG. 1 illustrates the configuration of an RFPGA 20, respectively, when configured for the Mth functional block of a function consisting of three or more functional blocks. As a convention, the current functional block, i.e., the functional block configured in RFPGA 20 at a given time, will be referred to as the Mth functional block. Thus, if the Mth functional block is the second functional block, the first functional block is referred to as the “M−1” functional block, the third functional block is the “M+1” functional block, the fourth functional block is the “M+2” functional block, and so on. Each functional block other than the first and last functional block will have associated therewith “M−1” storage elements, i.e., the outputs of the “M−1” functional block, which are the inputs to the Mth functional block, and “M” storage elements, which contain the outputs of the Mth functional block. The first functional block does not need any “M−1” storage elements since the input to the first functional block comes from circuitry (not shown) located outside RFPGA 20 via I/O elements 24, and the last functional block does not need any “M” storage elements since the output of the last functional block is passed out of the RFPGA. The same nomenclature is also to be applied to the cycling of the functional blocks from one to the next as reconfiguration and processing proceed. For example, if the reference cycle is denoted the “M” cycle, the immediately prior cycle is the “M−1” cycle and the next cycle is the “M+1” cycle.
RFPGA 20 generally includes an array of configurable logic blocks (CLBs) 28, or other (re)programmable logic elements, interconnected to one another via interconnect resources 32. CLBs 28 are the reconfigurable functional elements, e.g., logic gates, used to implement the logic of each functional block of the desired function and the storage elements needed to store data being passed from one functional block to the next. Each CLB 28 programmed as a functional element is shown as a square containing an “F,” each CLB programmed as a corresponding “M−1” storage element is shown as a square containing an “M−1” and each CLB programmed as a corresponding “M” storage element is shown as a square containing an “M.” RFPGA 20 is in electrical communication with I/O cells 24, which provide communication between the RFPGA and other circuits (not shown), e.g., memory, processor, communication or other circuits.
As shown in FIG. 1, conventional RFPGA programming techniques result in storage elements M−1, M of the first functional block being scattered across the array of CLBs 28 at locations that locally optimize the logic paths through functional elements. The problem with this approach begins to appear, however, when a programmer 36 responsible for reconfiguring (programming) RFPGA 20 with each set of functional block and storage elements goes to reprogram the RFPGA with the second (and subsequent) functional blocks and corresponding storage locations. To reprogram RFPGA 20, programmer 36 must take into account the locations of scattered storage elements M so as to not interfere with the data stored there, which is the input to the next functional block. The process of optimizing a functional block and its storage elements is hampered by the scattered nature of the storage elements from the previous functional block.
The scattered nature of storage elements M−1, M also degrades the overall performance and cycle time of the function being processed by RFPGA 20. The length of delay from a storage element to the worst-case entry point into the next functional block becomes the limiting factor in the cycle time of RFPGA 20. Moreover, depending upon the path delay per cycle, the cycle time would vary from one cycle to the next. This could cause the worst cycle frequency to determine the overall processing speed of the function. This problem is directly dependent on the placement of the storage elements to determine the operating frequency of the function.
The ability of the programmer to place storage elements at appropriate locations to facilitate fast cycle times becomes dependent on not just the current functional block configuration requirements, but also on all subsequent functional block configuration requirements. That is, the locations of storage elements for the current functional block configuration affects the locations of the storage elements for the next functional block configuration, which affects the locations of storage elements for the following functional block configuration, and so on. This creates a combinatorial explosion of possible options for which the programmer must find a maximum cycle time for each cycle and an overall cycle time. For complex functional blocks, conventional RFPGA programmers can take several hours to produce a viable solution for one functional block configuration or cycle. It is readily seen that achieving a viable solution for multiple functional block configurations can require a prohibitive amount of time. A need therefore exists for configuring functional blocks in an efficient manner.